package com.zy.algorithm.model;

import java.util.ArrayDeque;
import java.util.List;
import java.util.Optional;

/**
 * @author ZhaoYi
 * @date 2023/12/25 16:44
 * 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
 */
public class Heap<T extends Comparable<? super T>> extends CompleteBinaryTree<T> {


    /**
     * 入堆排序操作，从数组最后一个位置插入，然后再与其父节点(i-1)/2比较大小，大则交换上去，接着往其爷节点持续走..直到顶，或小于当前节点的父节点则停止，完成排序
     *
     * @param t
     */
    @Override
    public void add(T t) {
        //先放进去
        super.add(t);
        //比较
        int index = getSize() - 1;
        Optional<NodeData<T>> parent = getParent(index);
        while (parent.isPresent() && t.compareTo(parent.get().getData()) > 0) {
            Integer pIndex = parent.get().getIndex();
            //交换
            swapByIndex(index, pIndex);
            parent = getParent(pIndex);
            index = pIndex;
        }
    }

    public void printHeap() {
        List<T> data = getData();
        if (data.isEmpty()) {
            System.out.println("空");
            return;
        }
        NodeData<T> tNodeData = new NodeData<>(data.get(0), 0);
        ArrayDeque<NodeData<T>>  arrayDeque = new ArrayDeque<>();
        arrayDeque.add(tNodeData);
        prints(arrayDeque);
    }

    private void prints(ArrayDeque<NodeData<T>> arrayDeque) {
        while (!arrayDeque.isEmpty()){
            NodeData<T> tNodeData = arrayDeque.removeFirst();
            System.out.print(tNodeData);

            Optional<NodeData<T>> left = getLeft(tNodeData.getIndex());
            Optional<NodeData<T>> right = getRight(tNodeData.getIndex());


            left.ifPresent(arrayDeque::add);
            right.ifPresent(arrayDeque::add);


        }
    }




    /*private void prints(Optional<NodeData<T>> tNodeData) {
        if (!tNodeData.isPresent()){
            return;
        }
        System.out.print("data = " + tNodeData);
        Optional<NodeData<T>> left = getLeft(tNodeData.get().getIndex());
        Optional<NodeData<T>> right = getRight(tNodeData.get().getIndex());

    }*/




    private void swapByIndex(int index, Integer pIndex) {
        List<T> data = getData();
        T tmp = data.get(index);
        data.set(index, data.get(pIndex));
        data.set(pIndex, tmp);
    }
}
